package com.jn.algorithm.day008.question24;

/**
 * @author 江南大学1033190417
 * @date 2022/4/22 14:03
 */
public class Solution {

    //迭代
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;
    }

    //自己写
    public ListNode mySwapPairs(ListNode head) {
        ListNode pre=new ListNode(-1);
        pre.next=head;
        ListNode temp=pre;
        while (temp.next!=null&&temp.next.next!=null){
            ListNode l1=temp.next;
            ListNode l2=temp.next.next;
            temp.next=l2;
            l1.next=l2.next;
            l2.next=l1;

            temp=l1;
        }
        return pre.next;
    }

    //递归
    public ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs2(newHead.next);
        newHead.next = head;
        return newHead;
    }


    public void print(ListNode node) {
        while (node != null) {
            System.out.print(node.val + "\t");
            node = node.next;
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);
        l1.next.next.next = new ListNode(3);
        Solution solution = new Solution();
        solution.print(solution.mySwapPairs(l1));
    }


}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
